import java.util.Deque;
import java.util.LinkedList;

public class num42 {
    //接雨水
    public int trap(int[] height) {
        Deque<Integer> stack = new LinkedList<>();
        int i = 0,ans = 0;
        while (i < height.length) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty())
                    break;
                int len = i - stack.peek() - 1;
                int high = Math.min(height[i],height[stack.peek()]) - height[top];
                ans += len * high;
            }
            stack.push(i);
            i ++;
        }
        return ans;
    }
}
